LuoguP2280 [HNOI2003] 激光炸弹 题解

#include <algorithm>
#include <iostream>
using namespace std;
// #define int long long

const int MaxN = 5e3+5;
int N,M,Arr[MaxN][MaxN],MaxI,MaxJ,Ans;

signed main(){
    cin>>N>>M;
    for (int i=1; i<=N; i++) {
        int x,y,v;
        cin>>x>>y>>v;
        Arr[y+1][x+1] = v;
        MaxI = max(MaxI,max(y+1,x+1));
        // MaxJ = max(MaxJ,x+1);
    }
    for (int i=1; i<=MaxI; i++) {
        for (int j=1; j<=MaxI; j++) {
            Arr[i][j]+=Arr[i-1][j]+Arr[i][j-1]-Arr[i-1][j-1];
            // cout<<Arr[i][j]<<" ";
        }
        // cout<<"\n";
    }
    for (int i=1; i<=MaxI-M+1; i++) {
        for (int j=1; j<=MaxI-M+1; j++) {
            // cout<<Arr[i+M-1][j+M-1]-Arr[i-1][j+M-1]-Arr[i+M-1][j-1]+Arr[i-1][j-1]<<" ";
            Ans=max(Ans,Arr[i+M-1][j+M-1]-Arr[i-1][j+M-1]-Arr[i+M-1][j-1]+Arr[i-1][j-1]);
        }
        // cout<<"\n";
    }
    cout<<Ans<<"\n";
}